package com.javaDemo.ti;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

// /**
//   @ClassName: ErChaShuCengXubBanLi
//   @Auther: csy 二叉树层序遍历
//   @Date: 2021/3/31 01:10
//   @Description:
//  /
public class ErChaShuCengXubBanLi {

  public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    // int n=queue.size();
    // // while(n-->0){  //while (--n >= 0) {...}
    // //
    // // }
    public static void main(String[] args) {
        TreeNode node=new TreeNode(3);
        node.left=new TreeNode(9);
        node.right=new TreeNode(20,new TreeNode(15),new TreeNode(7));
        List<List<Integer>> levelOrder = new LinkedList<List<Integer>>();

        // Queue<TreeNode> queue=new LinkedList<>();
        // queue.offer(node);
        // while(!queue.isEmpty()){
        //     List<Integer> level = new ArrayList<Integer>();
        //     int size = queue.size();
        //     for(int i = 0; i < size; i++){
        //         TreeNode no = queue.poll();
        //         level.add(no.val);
        //         TreeNode left = no.left, right = no.right;
        //         if (left != null) {
        //             queue.offer(left);
        //         }
        //         if (right != null) {
        //             queue.offer(right);
        //         }
        //     }
        //     levelOrder.add(0, level);
        // }
        // levelOrder=levelOrderBottom(node);
        //
        levelOrderBottom(node, 0);
        System.out.println(levelOrder);
    }
    //bfs
    public static List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> levelOrder = new LinkedList<List<Integer>>();
        if (root == null) {
            return levelOrder;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                TreeNode left = node.left, right = node.right;
                if (left != null) {
                    queue.offer(left);
                }
                if (right != null) {
                    queue.offer(right);
                }
            }
            levelOrder.add(0, level);
        }
        return levelOrder;
    }


    static List<List<Integer>> res = new ArrayList<>();

  //dfs
    public static void levelOrderBottom(TreeNode root, int level) {
        if (root == null) {
            return;
        }
        if (res.size() <= level) {
            res.add(0, new ArrayList<>());
        }
        res.get(res.size() - level - 1).add(root.val);
        levelOrderBottom(root.left, level + 1);
        levelOrderBottom(root.right, level + 1);
    }
}
